package cn.jdemo.algorithm.backtracking;


import java.util.ArrayList;
import java.util.List;

/**
 * N皇后: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 */
public class NQueens {
    public static void main(String[] args) {
        test01();
    }

    private static void test01() {
        List<List<String>> lists = solveNQueens(8);
        lists.forEach(System.out::println);
    }

    private static List<List<String>> RES = new ArrayList<>();

    public static List<List<String>> solveNQueens(int n) {
        char board[][]= new char[n][n];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                board[i][j] = '.';
            }
        }
        backTrackNQueens(board,0);
        return RES;
    }

    private static void backTrackNQueens(char[][] board, int row) {
        if (row == board.length){
            buidResult(board);
            return;
        }

        for (int i=0; i<board.length ; i++){
            if (!isValid(board,row,i)){
                continue;
            }
            board[row][i] = 'Q';
            backTrackNQueens(board,row+1);
            board[row][i] = '.';
        }
    }

    private static void buidResult(char[][] board) {
        int length = board.length;
        List<String> tmp = new ArrayList<>(length);
        for (int i=0;i<length;i++){
            StringBuilder sBuilder = new StringBuilder();
            for (int j=0;j<length;j++){
                sBuilder.append(board[i][j]);
            }
            tmp.add(sBuilder.toString());
        }
        RES.add(tmp);
    }

    private static boolean isValid(char[][] board, int row, int col) {
        int length = board.length;

        // 同一列
        for (int i=row; i>=0; i--){
            if ('Q' == board[i][col]){
                return false;
            }
        }

        // 左下
        for (int i=row-1,j=col-1; i>=0 && j>=0; i--,j--){
            if ('Q' == board[i][j]){
                return false;
            }
        }

        // 右下
        for (int i=row-1,j=col+1; i>=0 && j<length; i--,j++){
            if ('Q' == board[i][j]){
                return false;
            }
        }
        return true;
    }

}
